The present invention relates generally to the field of wireless telecommunication, and particularly to the field of wireless asynchronous transfer mode (ATM) scheduling technology.
Due to its ability to provide elaborate quality of service guarantees, asynchronous transfer mode (ATM) is deemed as one of the technologies of choice for wide area networks (WAN) as well as local access network (LAN). Multimedia services, such as speech, video conferencing and computer communications could be integrated and served under one unified network using the ATM technique. In parallel to the development of the ATM technology, wireless and mobile communication services have been growing in popularity exponentially. As the demand for better and more reliable services increases, the next generation wireless mobile networks may adopt such services and quality-of-service (QoS) guarantees as those present nowadays in wired ATM networks. For example, a large number of projects funded under the European Commission""s Advanced Communication Technologies and Services (ACTS) programs are focused on research related to third generation mobile communication systems such as the Universal Mobile Telecommunications System (UMTS). Wireless ATM (WATM) can be considered as a very good candidate to implement QoS enabled wireless access networks that would fit well within the UMTS framework. Unlike other wireless LAN proposals, such as the IEEE 802.11, WATM can provide much more elaborate QoS guarantees.
The scarce bandwidth on the air interface, the high bit error rates that can occur on the wireless channel, and the inherent characteristic of the air interface being a broadcast channel, make the design of radio access layer (RAL) design a dramatically important step in WATM networks development. Recently, there has been intensive research on wireless ATM, with a strong emphasis on medium access control protocols (MAC) as well as data link control protocols (DLC). Most industry funded WATM proposals share some common important aspects.
In many of the systems, a WATM network contains one access point (AP) with several wireless terminals (WT). All communications between access point and wireless terminals are done through the multiple access channel. An efficient MAC protocol supports both up link and down link communications by using dynamic time division multiple access (D-TDMA) and time division duplexing (TDD) to provide flexible resources allocation at low cost. The problem with D-TDMA/TDD MAC protocol is that the bandwidth allocation to each user is time varying. Users compete to access the shared medium. Thus, channel management is essential and can be done by the access point. Centralized packet reservation multiple access (C-PRMA) proved to be an efficient means to implement D-TDMA protocol: instead of a fixed allocation of time slots like in second generation mobile networks (GSM), the wireless terminals obtain bandwidth only after requesting it from the AP by either using a random access channel or by piggy-backing their request to a data slot. The data unit of the MAC is a frame. It has one downlink period and one uplink period. During the downlink period the transmission is done only from the AP to the wireless terminals. The AP allocates time slots to connections and announces the allocation in the broadcast field which is part of the down link period. Announcement list and allocation list define the layout of the frame, i.e., in which time slots the terminals are expected to send their cells and in which others should they expect to receive the cells. To reduce further the protocol overhead, slots carrying uplink traffic from the same wireless terminal in a given frame are grouped into a cluster. Physical header and cluster header are appended to the cluster rather than to the individual cells. FIG. 1 shows the structure of this generic MAC frame.
In ATM systems, connections can fall into one of five service classes. They are constant bit-rate (CBR), real-time variable bit-rate (rt-VBR), non-realtime variable bit-rate (nrt-VBR), available bit-rate (ABR) and unspecified bit-rate (UBR). CBR is characterized by the peak cell rate (PCR), maximum tolerable cell transfer delay (maxCTD) and cell loss ratio (CLR). Since for an end-to-end ATM connection the cell delay variation introduced in the wireless part of the connection is expected to be negligible compared to the one introduced in the wired part, we assume that the CDV introduced in the wireless part can be xe2x80x9cabsorbedxe2x80x9d by the AP who performs traffic shaping before forwarding the cells to the wired part of the network. Rt-VBR is characterized by PCR, sustained cell rate (SCR), maxCTD and CLR. nrt-VBR has only PCR, SCR and CLR as parameters. An ABR source is characterized by its minimum cell rate (MCR). UBR does not declare any traffic descriptors and has no quality of service guarantees. In a multi-hop connection like it is the case in wired ATM, the different traffic classes are often segregated in the multiplexers and a static priority among different classes applied. In wireless ATM, especially because of the centralized bandwidth allocation at the AP, as well as the dynamic bandwidth reservation approach, these heterogeneous services can be grouped into two major categories: real time traffics, and non-real time traffics. Real time traffics that include CBR and rt-VBR, require a tight and bounded quality of service with throughput, end-to-end delay, error tolerance. In contrast, non-real time traffics, i.e. nrt-VBR, ABR and UBR, are more elastic with respect to performance guarantees at the ATM layer and below.
Scheduling is a key element when multiplexing different categories of traffic while providing good performance. However, it is not easy to guarantee QoS on a wireless medium for the intrinsic problems of the air interface described previously. Another major consideration, other than the inherent problems of the channel, to take into account for designing scheduling mechanisms in wireless environment is the remote queue problem. The uplink queues in wireless systems are located at the terminals and thus they are regarded as remote queues. The AP has no idea about the queue status unless the wireless terminal exchanges information with it on the issue. How this information is exchanged impacts dramatically the throughput of the MAC as well as the sustained QoS:
(i) to sustain tight QoS bounds, accurate per-cell information, such as cell due date, or virtual times, need to be transferred to the AP;
(ii) by the time the information reaches the AP and is used to estimate the bandwidth to allocate to a given terminal, the queue status might change, and thus the amount of bandwidth allocated to a given wireless terminal does not reflect the queue status at the time immediately before transmission occurs.
This requires a xe2x80x9csmartxe2x80x9d choice of reservation technique to compromise between protocol throughput and QoS requirements. Smart choice here means exchanging as little information as possible while still providing relatively tight QoS bounds.
The above description leads to the basic criteria for a scheduler for WATM networks. Firstly, the scheduler must be able to serve heterogeneous classes of traffic and make use the available information to perform resources sharing with QoS guarantee; secondly, it has to cooperate with the MAC seamlessly and make use of the MAC effectively; thirdly, any protocol overhead that the scheduler introduces should be as small as possible; finally, the scheduler must cope with the remote queue problem.
The present distributed scheduling architecture comprises a hierarchy of schedulers comprising one master scheduler and many slave schedulers. The master scheduler is located at the AP. Its basic role is to allocate physical bandwidth to the different terminals. The slave scheduler is located in the data link control layer of a wireless terminal and one is located in the AP. It is important to note that at the AP, both master scheduler and slave scheduler (AP) co-exist while at the wireless terminals only slave schedulers (WT) are implemented. The rationale behind this architecture, is that the AP allocates time slots to the wireless terminals based on the information it receives through the reservation protocol, however, to cope with the problem of this information being out of date, the wireless terminals are allowed to freely distribute the allocated slots among their connections.